package 链表题目;

import 链表题目.model.ListNode;

//环型链表2
//https://leetcode.cn/problems/linked-list-cycle-ii/description/?envType=problem-list-v2&envId=59jEaTgw
//给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
public class 环型链表2 {
    public ListNode detectCycle(ListNode head) {
    /*if (head == null || head.next == null) {
            return null;
        }
        HashSet<ListNode> listNodes = new HashSet<>();
        while (head != null) {
            if (listNodes.contains(head)) {
                return head;
            }
            listNodes.add(head);
            head = head.next;
        }
        return null;*/
        if (head == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next == null) {
                return null;
            } else {
                fast = fast.next.next;
            }
            if (fast == slow) {
                // 存在环，从头遍历最先的环节点
                ListNode temp = head;
                while (temp != slow) {
                    temp = temp.next;
                }
                return temp;
            }
        }
        return null;
    }
}
